home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / graph / testall.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  4.2 KB  |  225 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/ugraph.h>
  3. #include <LEDA/graph_alg.h>
  4.  
  5. #include <ctype.h>
  6.  
  7.  
  8.  
  9. main()
  10. {
  11.   GRAPH<string,double> G;
  12.  
  13.   random_graph(G,10,30);
  14.  
  15.   edge_array<int>  cost(G);
  16.   node_array<int>  dist(G);
  17.   node_array<edge> pred(G);
  18.  
  19.   node_array<int>  ord(G);
  20.   node_array<int>  compnum(G);
  21.   edge_array<int>  flow(G) ;
  22.   node_array<bool> reached(G,false);
  23.   node_array<int>  dfs_num(G);
  24.   node_array<int>  comp_num(G);
  25.   node_array<int>  layer(G,-1);
  26.  
  27.   node_matrix<int> M(G);
  28.  
  29.   list<node> nl;
  30.   list<edge> el;
  31.  
  32.   node       v,w,s,t;
  33.   edge       e;
  34.  
  35.  
  36.   UGRAPH<string,double> U = G;
  37.  
  38.   node_array<int> compnum1(U);
  39.  
  40.   init_random();
  41.   forall_edges(e,G)  G[e] = cost[e] = random(0,1000);
  42.  
  43.  
  44.  
  45.   cout << "TOPSORT:\n";
  46.   if (TOPSORT(G,ord)) 
  47.      cout << "graph is acyclic\n";
  48.   else 
  49.      cout << "graph is cyclic\n";
  50.   newline;
  51.  
  52.   newline;
  53.   cout << "DFS:\n";
  54.   newline;
  55.   nl = DFS(G,G.choose_node(),reached);
  56.   forall(v,nl) { G.print_node(v); newline; }
  57.   newline;
  58.  
  59.   newline;
  60.   cout << "DFS_NUM:\n";
  61.   DFS_NUM(G,dfs_num,comp_num);
  62.   forall_nodes(v,G) 
  63.   { G.print_node(v);
  64.     cout << string("  dfsnum = %2d  compnum = %2d \n",dfs_num[v],comp_num[v]);
  65.    }
  66.   newline;
  67.  
  68.   newline;
  69.   cout << "BFS:\n";
  70.   nl = BFS(G,G.first_node(),layer);
  71.   forall_nodes(v,G)
  72.   { G.print_node(v);
  73.     cout << string("  layer = %2d\n",layer[v]);
  74.    }
  75.   newline;
  76.  
  77.  
  78.   newline;
  79.   cout << "COMPONENTS:\n";
  80.   COMPONENTS(U,compnum1);
  81.   forall_nodes(v,U)
  82.   { U.print_node(v);
  83.     cout << string("  compnum = %2d \n",compnum1[v]);
  84.    }
  85.   newline;
  86.  
  87.   newline;
  88.   cout << "COMPONENTS1:\n";
  89.   COMPONENTS1(U,compnum1);
  90.   forall_nodes(v,U)
  91.   { U.print_node(v);
  92.     cout << string("  compnum = %2d \n",compnum1[v]);
  93.    }
  94.   newline;
  95.  
  96.  
  97.   newline;
  98.   cout << "TRANSITIVE_CLOSURE:\n";
  99.   graph G1 = TRANSITIVE_CLOSURE(G);
  100.   G1.print("Graph G1 = transitive closure of G");
  101.   newline;
  102.  
  103.   newline;
  104.   cout << "SPANNING_TREE: \n";
  105.   el = SPANNING_TREE(G);
  106.   forall(e,el) 
  107.     { G.print_edge(e);;
  108.       newline;
  109.      }
  110.   newline;
  111.  
  112.   cout << "MIN_SPANNING_TREE: \n";
  113.   el = MIN_SPANNING_TREE(G,cost);
  114.   forall(e,el) 
  115.   { G.print_edge(e);;
  116.     newline;
  117.    }
  118.  
  119.  
  120.   newline;
  121.   cout << "STRONG_COMPONENTS:\n";
  122.   STRONG_COMPONENTS(G,compnum);
  123.   forall_nodes(v,G) 
  124.   { G.print_node(v);
  125.     cout << string("  compnum = %d\n",compnum[v]);
  126.    }
  127.   newline;
  128.  
  129.  
  130.   s = G.first_node();
  131.  
  132.   float T = used_time();
  133.  
  134.   newline;
  135.   cout << "DIJKSTRA <int>      ";
  136.   cout.flush();
  137.   DIJKSTRA(G,s,cost,dist,pred);
  138.   cout << string("%6.2f sec  \n",used_time(T));
  139.   newline;
  140.  
  141.   cout << "BELLMAN_FORD <int>  ";
  142.   cout.flush();
  143.   BELLMAN_FORD(G,s,cost,dist,pred);
  144.   cout << string("%6.2f sec  \n",used_time(T));
  145.   newline;
  146.  
  147.   cout << "ALL PAIRS SHORTEST PATHS <int> ";
  148.   cout.flush();
  149.   ALL_PAIRS_SHORTEST_PATHS(G,cost,M);
  150.   cout << string("%.2f sec\n",used_time(T));
  151.   forall_nodes(v,G)
  152.   { forall_nodes(w,G) cout << string("%7d ",M(v,w));
  153.     newline;
  154.    }
  155.   newline;
  156.  
  157.  
  158.   cout << "MAX_FLOW<int>:  ";
  159.   cout.flush();
  160.   s = G.first_node();
  161.   t = G.last_node();
  162.   int val = MAX_FLOW(G,s,t,cost,flow) ;
  163.   cout << string("total flow = %d \n",val);
  164.   newline;
  165.  
  166.  
  167.  
  168.  
  169.   edge_array<double>  cost1(G);
  170.   node_array<double>  dist1(G);
  171.   edge_array<double>  flow1(G) ;
  172.   node_matrix<double> M1(G);
  173.  
  174.   forall_edges(e,G)  cost1[e] = cost[e];
  175.  
  176.  
  177.   used_time(T);
  178.   cout << "DIJKSTRA <double>     ";
  179.   cout.flush();
  180.   DIJKSTRA(G,s,cost1,dist1,pred);
  181.   cout << string("%6.2f sec  \n",used_time(T));
  182.   newline;
  183.  
  184.  
  185.   cout << "BELLMAN_FORD <double> ";
  186.   cout.flush();
  187.   BELLMAN_FORD(G,s,cost1,dist1,pred);
  188.   cout << string("%6.2f sec  \n",used_time(T));
  189.   newline;
  190.  
  191.  
  192.   cout << "ALL PAIRS SHORTEST PATHS <double>  ";
  193.   cout.flush();
  194.   ALL_PAIRS_SHORTEST_PATHS(G,cost1,M1);
  195.   cout << string("%.2f sec\n",used_time(T));
  196.   newline;
  197.  
  198.   cout << "MAX_FLOW<double>: ";
  199.   cout.flush();
  200.   double val1 = MAX_FLOW(G,s,t,cost1,flow1) ;
  201.   cout << string("total flow = %f \n",val1);
  202.   newline;
  203.  
  204.  
  205.   if (PLANAR(G)) 
  206.     { cout << "G is planar\n";
  207.       //cout << "STRAIGHT_LINE_EMBEDDING: \n";
  208.       //node_array<int>   xcoord(G);
  209.       //node_array<int>   ycoord(G);
  210.       //STRAIGHT_LINE_EMBEDDING(G,xcoord,ycoord);
  211.       //forall_nodes(v,G) 
  212.       //{ G.print_node(v);
  213.       //  cout << string("  x = %3d   y = %3d\n",xcoord[v],ycoord[v]);
  214.       // }
  215.       // newline;
  216.      }
  217.   else 
  218.     cout << "G is not planar\n";
  219.  
  220.   newline;
  221.  
  222.   return 0;
  223.  
  224. }
  225.